package algorithm.dynamic_programming;

public class KillMonster {

    public static double killMonsterPossible(int N, int K, int M){
        if(N == 0 || K== 0)
            return 0;
        int process = process(N, K, M);
        return process/Math.pow(M + 1, K);
    }

    public static int process(int hp, int times, int M){
        if(times == 0)
           return hp <= 0? 1 : 0;
        if(hp <= 0)
            return (int)Math.pow(M + 1, times);
        int result = 0;
        for (int i = 0; i <= M; i++) {
            result += process(hp - i, times - 1, M);
        }
        return result;
    }

    public static double killMonsterPossible2(int N, int K, int M){
        int[][] dp = new int[K + 1][N + 1];
        int times = dp.length;
        int hp = dp[0].length;
        dp[0][0] = 1;
        for (int i = 1; i < times; i++) {
            dp[i][0] = (int) Math.pow(M + 1, i);
            for (int j = 1; j < hp; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                if(j - 1 - M >= 0)
                    dp[i][j] -= dp[i - 1][j - 1 - M];
                else
                    dp[i][j] -= Math.pow(M + 1, i - 1);
            }
        }
        return dp[K][N]/Math.pow(M + 1, K);
    }

    public static void main(String[] args) {
        double v = killMonsterPossible(10, 5, 5);
        double v2 = killMonsterPossible2(10, 5, 5);
        System.out.println(v);
        System.out.println(v2);
    }
}
